package leetcode.median;

/**
 * ClassName: $581_FindUnsortedSubarray
 * Description:
 * date: 2022-02-19 12:26
 *
 * @author liyifan
 */
public class $581_FindUnsortedSubarray {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        // 维护一个右侧最小值数组
        int[] rightMin = new int[len];
        rightMin[len - 1] = nums[len - 1];
        // 维护一个左侧最大值数组
        int[] leftMax = new int[len];
        leftMax[0] = nums[0];

        for (int i = len - 2;i >= 0;i--) {
            rightMin[i] = Math.min(nums[i], rightMin[i + 1]);
        }
        for (int i = 1;i < len;i++) {
            leftMax[i] = Math.max(nums[i], leftMax[i - 1]);
        }
        // 双指针遍历
        int left = -1;
        int right = len - 1;
        for (int i = 0;i < len;i++) {
            if (nums[i] > rightMin[i]) {
                left = i;
                break;
            }
        }
        if (left == -1) return 0;

        for (int i = len - 1;i >= 0;i--) {
            if (nums[i] < leftMax[i]) {
                right = i;
                break;
            }
        }
        return right - left + 1;
    }
}
